W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W tym zadaniu wcielasz się w jurora Olimpiady Informatycznej. Pracujesz właśnie nad przygotowaniem testów do jednego z zadań. Znalazłaś/znalazłeś wadliwe rozwiązanie i teraz musisz przygotować testy, których to rozwiązanie nie przejdzie. Niniejsze zadanie składa się z trzech podzadań. Twoim zadaniem jest napisanie jednego programu, który na podstawie danych wejściowych zorientuje się, z którym podzadaniem ma do czynienia, i znajdzie rozwiązanie dla tego podzadania.
Ponieważ Twoje rozwiązania będą generować testy, powinny one wypisywać dane w dokładnie takim formacie, jak w podanej specyfikacji. Należy zadbać o odpowiednie wypisywanie odstępów i znaków nowego wiersza. W szczególności, na końcu wyjścia należy zawsze wypisać dokładnie jeden znak nowego wiersza.
Uwaga. Za to zadanie można zdobyć w sumie punktów.
W zadaniu dany jest ciąg liczb całkowitych, który należy posortować. W pliku quicksort.cpp znajduje się rozwiązanie, które implementuje algorytm Quicksort. To rozwiązanie, z powodu użytego sposobu wyboru elementu dzielącego, może działać wolno. Twoim zadaniem jest napisanie programu, który generuje takie testy, dla których łączna liczba iteracji dwóch wewnętrznych pętli while w funkcji quicksort będzie równa co najmniej .
W pierwszym i jedynym wierszu wejścia znajduje się słowo sortowanie, po którym następuje liczba ().
Twój program powinien wypisać dane wejściowe dla programu quicksort.cpp w następującym formacie. W pierwszym wierszu wyjścia powinna znaleźć się liczba wczytana z wejścia. W drugim wierszu powinien znaleźć się ciąg liczb całkowitych ().
W zadaniu dana jest kwadratowa plansza o wymiarach złożona z kwadratowych pól. Po planszy porusza się pionek. W każdym ruchu pionek może przesunąć się na jedno z czterech pól sąsiadujących z polem, na którym aktualnie się znajduje. Niektóre pola planszy są zabronione i pionek nie może się nigdy na nich znaleźć. Pozostałe pola nazywamy polami dostępnymi. Celem zadania jest obliczenie, dla każdego pola dostępnego, w ilu ruchach pionek może się na nie dostać. Poprawne rozwiązanie tego zadania znajduje się w pliku bfs_poprawny.cpp. Zawiera ono implementację algorytmu BFS na podstawie szablonu queue z STL.
Łatwo jednak popełnić pewien (nieoczywisty) błąd i w rozwiązaniu użyć takiej implementacji kolejki, która zakłada, że każdym momencie w kolejce będzie co najwyżej elementów. W tym podzadaniu Twój program powinien wypisać test, dla którego powyższa procedura w pewnym momencie w trakcie wykonania będzie przechowywać w kolejce więcej niż elementów.
W pierwszym i jedynym wierszu wejścia znajduje się słowo bfs, po którym następuje liczba ().
Twój program powinien wypisać dane wejściowe dla programu bfs_poprawny.cpp w następującym formacie. Pierwszy wiersz powinien zawierać liczbę wczytaną z wejścia, a następnie dwie liczby i (). Oznaczają one, że pionek startuje na polu w wierszu i kolumnie .
Dalej powinien znajdować się opis planszy w postaci wierszy po znaków # i/lub . - znaki te oznaczają odpowiednio pole zabronione i pole dostępne. Pole startowe musi być polem dostępnym.
Dla podanej planszy, w programie bfs_poprawny.cpp do kolejki powinno być wstawione więcej niż elementów.
W zadaniu należy napisać algorytm znajdujący najkrótsze ścieżki w grafie nieskierowanym, w którym krawędzie mają długości wyrażone dodatnimi liczbami całkowitymi. Graf składa się z wierzchołków, które numerujemy . Celem jest znalezienie odległości od wierzchołka do każdego wierzchołka grafu. Poprawne rozwiązanie znaleźć można w pliku dijkstra_poprawna.cpp. Implementuje ono (nieco zmodyfikowany) algorytm Dijkstry przy użyciu priority_queue, czyli kolejki priorytetowej z STL.
Jeden z błędów, jaki można tu popełnić, to użycie zwykłej kolejki w miejscu kolejki priorytetowej. Taka implementacja znajduje się w pliku dijkstra_wolna.cpp. Wprawdzie jest ona poprawna, jednak czasem działa znacznie wolniej.
Twoim zadaniem jest napisanie programu, który będzie generować testy, dla których wewnętrzna pętla for w drugim programie wykona co najmniej 20 razy więcej obrotów niż analogiczna pętla w pierwszym programie.
W pierwszym i jedynym wierszu wejścia znajduje się słowo sciezki, po którym następuje liczba całkowita ().
Twój program powinien wypisać wejście dla programów dijkstra_poprawna.cpp oraz dijkstra_wolna.cpp w następującym formacie. W pierwszym wierszu wyjścia powinny znaleźć się: liczba wczytana z wejścia oraz liczba całkowita (). Liczba oznacza liczbę wierzchołków, zaś - liczbę krawędzi grafu. W kolejnych wierszach powinny znaleźć się opisy poszczególnych krawędzi grafu. Opis jednej krawędzi powinien składać się z trzech liczb całkowitych , , (, , ). Dla każdych dwóch wierzchołków może istnieć co najwyżej jedna krawędź, która je łączy. Każda krawędź grafu powinna zostać wypisana dokładnie raz. Musi istnieć co najmniej jedna krawędź o końcu w wierzchołku .
Autor zadania: Jakub Łącki.